We present a novel complex number formulation along with tight convexrelaxations for the aircraft conflict resolution problem. Our approach combinesboth speed and heading control and provides global optimality guaranteesdespite non-convexities in the feasible region. As a side result, we present anew characterization of the conflict separation condition in the form ofdisjunctive linear constraints. Our formulation features one binary variableper pair of aircraft, is free of trigonometric functions, and captures thenon-convexity in a set of quadratic concave constraints. Using our approach, weare able to close a number of open instances and reduce computational time byup to two orders of magnitude on standard instances.
展开▼
